package stack.easy;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1. 问题描述
 *      请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
 *      执行push、pop和min操作的时间复杂度必须为O(1)。
 *
 * 2. 算法分析
 *      题目很简单，但是简单的题目也有比较新颖的做法，下面的解法2，解法3都是比较独特的思路，对解法1在空间上的优化
 *      解法4从底层数据结构的角度出发，使用链表来实现最小栈
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 面试题0302栈的最小值 {
    class MinStack1 {

        // 实现一个单调栈
        // 维护栈顶的元素是最小的

        // -2 0 -3 入栈


        Deque<Integer> stack1; // 正常栈
        Deque<Integer> stack2; // 单调栈 此栈维护栈顶元素的单调性


        /** initialize your data structure here. */
        public MinStack1() {
            stack1 = new ArrayDeque<>();
            stack2 = new ArrayDeque<>();
        }

        public void push(int x) {
            stack1.push(x); // 按照正常的栈进行入栈即可
            // 维护单调栈
            if(stack2.isEmpty()) {
                // 如果单调栈空
                stack2.push(x);
                return;
            }
            // 当前入栈元素和栈顶元素比较
            if(stack2.peek() >= x) {
                stack2.push(x); // 直接入栈
            } else {
                int top = stack2.pop(); // 取出当前栈顶元素
                stack2.push(x);
                stack2.push(top);
            }
        }

        // 问题在于没有更新top的指向，如果找到
        public void pop() {
            if(stack1.isEmpty()) {
                return;
            }
            int top = stack1.pop();
            stack2.remove(top); // 注意删除正常栈的元素时，还需要将该元素从单调栈中删除
        }

        public int top() {
            if(stack1.isEmpty()) {
                return -1;
            }
            return stack1.peek();
        }

        public int getMin() {
            return stack2.peek();
        }
    }


    /**
     * 对于上述代码的优化
     * stack的作用就是记录入栈，support的作用就是记录当前入栈元素的最小值
     * 具体栈顶元素保留的是当前已入栈stack中的最小值，
     *
     * 对于入栈操作：
     *  首先x直接入栈stack，因为stack就是普通栈
     *  其次对于support，如果为空，直接入栈，如果不为空，与当前栈顶元素进行比较
     *  如果当前入栈元素小于等于support栈顶元素，入栈(注意此时是小于等于，而不是
     *  严格小于，因为最小元素未必唯一，如果是严格小于，如果出现两个最小值但是此时
     *  我们只能记录一次，则会有最小值的信息丢失)
     *
     *  对于出栈操作，每次出栈我们将当前出栈元素和support中的栈顶元素做比较，如果相同，
     *  说明此时我们将当前入栈元素中的最小值删除，此时需要更新最小值，即删除support中的
     *  栈顶元素，为什么直接删除栈顶元素即可，因为support中从栈底到栈顶是入栈元素从小到
     *  大的，也就是说stack中的元素只能大于等于support中的栈顶，不可能出现小于的情况
     */
    class MinStack {
        // 双栈实现
        Deque<Integer> stack; // 正常栈
        Deque<Integer> support; // 辅助栈 维护单调性
        /** initialize your data structure here. */
        public MinStack() {
            stack = new ArrayDeque<>();
            support = new ArrayDeque<>();
        }

        // 每次将栈顶元素设置为当前最小元素
    /*
        入栈操作：
            对于stack而言，直接入栈
            对于support而言，如果栈为空，直接入栈，如果栈不空，将当前入栈的元素与栈顶元素进行比较
            如果小于等于栈顶，直接入栈(此处一定是小于等于，因为最小元素可能不唯一，有重复的，所以
            并不能直接考虑严格小于的)
            对于support栈而言，他当前入栈的元素一定是当前的元素中的最小值(不一定唯一)，
    */
        public void push(int x) { // O(1)
            stack.push(x);
            if(support.isEmpty()) {
                support.push(x);
            } else if(x <= support.peek()){
                support.push(x);
            }
        }

        public void pop() { // O(1)
            if(stack.isEmpty()) {
                return;
            }
            // 注意此时我们并不能直接删除元素就完事了，需要判断当前删除的元素是否为support中的栈顶元素
            // 如果删除了，但是support中的栈顶元素没有修改，则下一次取出的最小值就不是当前栈中的最小值
            // 删除之后，当前栈顶就是最小值了，原因是我们每次都是将当前最小值入栈support，所以当我们删
            // 除已经入栈的元素一定比support栈中的元素大
            int temp = stack.pop();
            if(temp == support.peek()) {
                support.pop();
            }
        }

        // 居然不抛出空指针异常?????
        public int top() { // O(1)
            return stack.peek();
        }

        public int getMin() { // O(1)
            return support.peek();
        }
    }




    /**
     * 如果不采用额外的空间实现下述结构 采用一个整形变量记录最小值
     * 但是有个问题就是当前记录的最小值，在栈进行出栈操作之后未必是
     * 出栈之后的最小值，所以如果采用一个栈实现的难点之处就是如何记录
     * 上一次的最小值
     */
    class MinStack2 {

        /** initialize your data structure here. */
        public MinStack2() {

        }

        public void push(int x) {

        }

        // 问题在于没有更新top的指向，如果找到
        public void pop() {

        }

        public int top() {
            return -1;
        }

        public int getMin() {
            return -1;
        }
    }


    /**
     * 单栈的另外一种解法 保存差值法
     */
    class MinStack3 {

        /** initialize your data structure here. */
        public MinStack3() {

        }

        public void push(int x) {

        }

        // 问题在于没有更新top的指向，如果找到
        public void pop() {

        }

        public int top() {

            return -1;
        }

        public int getMin() {

            return -1;
        }
    }



    /**
     * 链表法
     */
    class MinStack4 {

        /** initialize your data structure here. */
        public MinStack4() {

        }

        public void push(int x) {

        }

        // 问题在于没有更新top的指向，如果找到
        public void pop() {

        }

        public int top() {

            return -1;
        }

        public int getMin() {

            return -1;
        }
    }

}
